package main.leetcode.clockin.April;

import java.util.Arrays;

/**
 * 1248.统计优美子数组
 *
 * <p>给你一个整数数组 nums 和一个整数 k。
 *
 * <p>如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
 *
 * <p>请返回这个数组中「优美子数组」的数目。
 *
 * <p>
 *
 * <p>示例 1：输入：nums = [1,1,2,1,1], k = 3 输出：2 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
 *
 * <p>示例 2：输入：nums = [2,4,6], k = 1 输出：0 解释：数列中不包含任何奇数，所以不存在优美子数组。
 *
 * <p>示例 3：输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2 输出：16
 *
 * <p>提示：1 <= nums.length <= 50000，1 <= nums[i] <= 10^5 1 <= k <= nums.length
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day21 {
    public static void main(String[] args) {
        //        System.out.println(new day21().numberOfSubarrays(new int[] {1, 1, 2, 1, 1}, 3));
        System.out.println(
                new day21().numberOfSubarrays(new int[] {2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1}, 2));
    }

    //    public int numberOfSubarrays(int[] nums, int k) {
    //        List<Integer> list = new ArrayList<>();
    //        for (int i = 0; i < nums.length; ++i) {
    //            if ((nums[i] & 1) == 1) {
    //                list.add(i);
    //            }
    //        }
    //        int size = list.size();
    //        if (size < k) {
    //            return 0;
    //        }
    //        int i = 0, j = k - 1;
    //        int res = 0;
    //        int l, r;
    //        while (j < size) {
    //            l = list.get(i) - (i > 0 ? list.get(i - 1) + 1 : 0);
    //            r = (j < size - 1 ? list.get(j + 1) - 1 : nums.length - 1) - list.get(j);
    //            res += l + r + l * r + 1;
    //            ++i;
    //            ++j;
    //        }
    //        return res;
    //    }

    // 优化
    //    public int numberOfSubarrays(int[] nums, int k) {
    //        int n = nums.length;
    //        int[] record = new int[n];
    //        int index = 0;
    //        int res = 0;
    //        for (int num : nums) {
    //            ++record[index];
    //            index += num & 1;
    //            if (index >= k) {
    //                res += record[index - k];
    //            }
    //            System.out.println(Arrays.toString(record));
    //        }
    //        return res;
    //    }

    // 滑动窗口
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        // +2，0号位记录-1，index+1号位记录n（应对全为奇数的输入）
        int[] record = new int[n + 2];
        int index = 0;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if ((nums[i] & 1) == 1) {
                record[++index] = i;
            }
        }
        record[0] = -1;
        record[index + 1] = n;
        System.out.println(Arrays.toString(record));
        for (int i = 1; i + k < index + 2; ++i) {
            res += (record[i] - record[i - 1]) * (record[i + k] - record[i + k - 1]);
        }
        return res;
    }
}
